home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / ImageMagick / magick / colors.c next >
Encoding:
C/C++ Source or Header  |  1994-08-02  |  10.9 KB  |  352 lines
  1. /*
  2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  3. %                                                                             %
  4. %                                                                             %
  5. %                                                                             %
  6. %                  CCCC   OOO   L       OOO   RRRR    SSSSS                   %
  7. %                 C      O   O  L      O   O  R   R   SS                      %
  8. %                 C      O   O  L      O   O  RRRR     SSS                    %
  9. %                 C      O   O  L      O   O  R R        SS                   %
  10. %                  CCCC   OOO   LLLLL   OOO   R  R    SSSSS                   %
  11. %                                                                             %
  12. %                                                                             %
  13. %                       Count the Colors in an Image                          %
  14. %                                                                             %
  15. %                                                                             %
  16. %                                                                             %
  17. %                           Software Design                                   %
  18. %                             John Cristy                                     %
  19. %                              July 1992                                      %
  20. %                                                                             %
  21. %                                                                             %
  22. %  Copyright 1994 E. I. du Pont de Nemours & Company                          %
  23. %                                                                             %
  24. %  Permission to use, copy, modify, distribute, and sell this software and    %
  25. %  its documentation for any purpose is hereby granted without fee,           %
  26. %  provided that the above Copyright notice appear in all copies and that     %
  27. %  both that Copyright notice and this permission notice appear in            %
  28. %  supporting documentation, and that the name of E. I. du Pont de Nemours    %
  29. %  & Company not be used in advertising or publicity pertaining to            %
  30. %  distribution of the software without specific, written prior               %
  31. %  permission.  E. I. du Pont de Nemours & Company makes no representations   %
  32. %  about the suitability of this software for any purpose.  It is provided    %
  33. %  "as is" without express or implied warranty.                               %
  34. %                                                                             %
  35. %  E. I. du Pont de Nemours & Company disclaims all warranties with regard    %
  36. %  to this software, including all implied warranties of merchantability      %
  37. %  and fitness, in no event shall E. I. du Pont de Nemours & Company be       %
  38. %  liable for any special, indirect or consequential damages or any           %
  39. %  damages whatsoever resulting from loss of use, data or profits, whether    %
  40. %  in an action of contract, negligence or other tortuous action, arising     %
  41. %  out of or in connection with the use or performance of this software.      %
  42. %                                                                             %
  43. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  44. %
  45. %
  46. %
  47. */
  48.  
  49. /*
  50.   Include declarations.
  51. */
  52. #include "magick.h"
  53. #include "image.h"
  54. /*
  55.   Define declarations.
  56. */
  57. #define MaxTreeDepth  8  /* Log2(MaxRGB) */
  58. #define NodesInAList  MaxTextLength
  59.  
  60. /*
  61.   Structures.
  62. */
  63. typedef struct _Node
  64. {
  65.   struct _Node
  66.     *child[8];
  67.  
  68.   unsigned char
  69.     level,
  70.     mid_red,
  71.     mid_green,
  72.     mid_blue;
  73.  
  74.   unsigned long
  75.     number_colors;
  76. } Node;
  77.  
  78. typedef struct _Nodes
  79. {
  80.   Node
  81.     nodes[NodesInAList];
  82.  
  83.   struct _Nodes
  84.     *next;
  85. } Nodes;
  86.  
  87. typedef struct _Cube
  88. {
  89.   Node
  90.     *root;
  91.  
  92.   unsigned int
  93.     colors;
  94.  
  95.   unsigned int
  96.     free_nodes;
  97.  
  98.   Node
  99.     *node;
  100.  
  101.   Nodes
  102.     *node_list;
  103. } Cube;
  104.  
  105. /*
  106.   Global variables.
  107. */
  108. static Cube
  109.   cube;
  110.  
  111. /*
  112. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  113. %                                                                             %
  114. %                                                                             %
  115. %                                                                             %
  116. %  H i s t o g r a m                                                          %
  117. %                                                                             %
  118. %                                                                             %
  119. %                                                                             %
  120. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  121. %
  122. %  Procedure Histogram traverses the color cube tree and produces a list of
  123. %  unique pixel field values and the number of times each occurs in the image.
  124. %
  125. %  The format of the Histogram routine is:
  126. %
  127. %      Histogram(node,file)
  128. %
  129. %  A description of each parameter follows.
  130. %
  131. %    o node: The address of a structure of type Node which points to a
  132. %      node in the color cube tree that is to be pruned.
  133. %
  134. %
  135. */
  136. static void Histogram(node,file)
  137. register Node
  138.   *node;
  139.  
  140. FILE
  141.   *file;
  142. {
  143.   register unsigned int
  144.     id;
  145.  
  146.   /*
  147.     Traverse any children.
  148.   */
  149.   for (id=0; id < 8; id++)
  150.     if (node->child[id] != (Node *) NULL)
  151.       Histogram(node->child[id],file);
  152.   if (node->level == MaxTreeDepth)
  153.     (void) fprintf(file,"%8lu\t%d\t%d\t%d\n",node->number_colors,
  154.       node->mid_red,node->mid_green,node->mid_blue);
  155. }
  156.  
  157. /*
  158. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  159. %                                                                             %
  160. %                                                                             %
  161. %                                                                             %
  162. %  I n i t i a l i z e N o d e                                                %
  163. %                                                                             %
  164. %                                                                             %
  165. %                                                                             %
  166. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  167. %
  168. %  Function InitializeNode allocates memory for a new node in the color cube
  169. %  tree and presets all fields to zero.
  170. %
  171. %  The format of the InitializeNode routine is:
  172. %
  173. %      node=InitializeNode(level,mid_red,mid_green,mid_blue)
  174. %
  175. %  A description of each parameter follows.
  176. %
  177. %    o level: Specifies the level in the classification the node resides.
  178. %
  179. %    o mid_red: Specifies the mid point of the red axis for this node.
  180. %
  181. %    o mid_green: Specifies the mid point of the green axis for this node.
  182. %
  183. %    o mid_blue: Specifies the mid point of the blue axis for this node.
  184. %
  185. %
  186. */
  187. static Node *InitializeNode(level,mid_red,mid_green,mid_blue)
  188. unsigned int
  189.   level,
  190.   mid_red,
  191.   mid_green,
  192.   mid_blue;
  193. {
  194.   register int
  195.     i;
  196.  
  197.   register Node
  198.     *node;
  199.  
  200.   if (cube.free_nodes == 0)
  201.     {
  202.       register Nodes
  203.         *nodes;
  204.  
  205.       /*
  206.         Allocate a new nodes of nodes.
  207.       */
  208.       nodes=(Nodes *) malloc(sizeof(Nodes));
  209.       if (nodes == (Nodes *) NULL)
  210.         return((Node *) NULL);
  211.       nodes->next=cube.node_list;
  212.       cube.node_list=nodes;
  213.       cube.node=nodes->nodes;
  214.       cube.free_nodes=NodesInAList;
  215.     }
  216.   cube.free_nodes--;
  217.   node=cube.node++;
  218.   for (i=0; i < 8; i++)
  219.     node->child[i]=(Node *) NULL;
  220.   node->level=level;
  221.   node->mid_red=mid_red;
  222.   node->mid_green=mid_green;
  223.   node->mid_blue=mid_blue;
  224.   node->number_colors=0;
  225.   return(node);
  226. }
  227.  
  228. /*
  229. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  230. %                                                                             %
  231. %                                                                             %
  232. %                                                                             %
  233. %  N u m b e r C o l o r s                                                    %
  234. %                                                                             %
  235. %                                                                             %
  236. %                                                                             %
  237. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  238. %
  239. %  Function NumberColors returns the number of unique colors in an image.
  240. %
  241. %  The format of the NumberColors routine is:
  242. %
  243. %      number_colors=NumberColors(image,file)
  244. %
  245. %  A description of each parameter follows.
  246. %
  247. %    o image: The address of a byte (8 bits) array of run-length
  248. %      encoded pixel data of your source image.  The sum of the
  249. %      run-length counts in the source image must be equal to or exceed
  250. %      the number of pixels.
  251. %
  252. %    o file:  An pointer to a FILE.  If it is non-null a list of unique pixel
  253. %      field values and the number of times each occurs in the image is
  254. %      written to the file.
  255. %
  256. %
  257. %
  258. */
  259. unsigned int NumberColors(image,file)
  260. Image
  261.   *image;
  262.  
  263. FILE
  264.   *file;
  265. {
  266.   Nodes
  267.     *nodes;
  268.  
  269.   register RunlengthPacket
  270.     *p;
  271.  
  272.   register int
  273.     i;
  274.  
  275.   register Node
  276.     *node;
  277.  
  278.   register unsigned int
  279.     count,
  280.     id,
  281.     level;
  282.  
  283.   unsigned int
  284.     bisect;
  285.  
  286.   /*
  287.     Initialize color description tree.
  288.   */
  289.   cube.node_list=(Nodes *) NULL;
  290.   cube.colors=0;
  291.   cube.free_nodes=0;
  292.   cube.root=InitializeNode(0,(MaxRGB+1) >> 1,(MaxRGB+1) >> 1,(MaxRGB+1) >> 1);
  293.   if (cube.root == (Node *) NULL)
  294.     {
  295.       Warning("Unable to count colors","Memory allocation failed");
  296.       return(0);
  297.     }
  298.   p=image->pixels;
  299.   for (i=0; i < image->packets; i++)
  300.   {
  301.     /*
  302.       Start at the root and proceed level by level.
  303.     */
  304.     count=p->length+1;
  305.     node=cube.root;
  306.     for (level=1; level <= MaxTreeDepth; level++)
  307.     {
  308.       id=(p->red >= node->mid_red ? 1 : 0) |
  309.         (p->green >= node->mid_green ? 1 : 0) << 1 |
  310.         (p->blue >= node->mid_blue ? 1 : 0) << 2;
  311.       if (node->child[id] == (Node *) NULL)
  312.         {
  313.           if (level == MaxTreeDepth)
  314.             {
  315.               node->child[id]=InitializeNode(level,(unsigned int) p->red,
  316.                 (unsigned int) p->green,(unsigned int) p->blue);
  317.               cube.colors++;
  318.             }
  319.           else
  320.             {
  321.               bisect=(unsigned int) (1 << (MaxTreeDepth-level)) >> 1;
  322.               node->child[id]=InitializeNode(level,
  323.                 node->mid_red+(id & 1 ? bisect : -bisect),
  324.                 node->mid_green+(id & 2 ? bisect : -bisect),
  325.                 node->mid_blue+(id & 4 ? bisect : -bisect));
  326.             }
  327.           if (node->child[id] == (Node *) NULL)
  328.             {
  329.               Warning("Unable to count colors","Memory allocation failed");
  330.               return(0);
  331.             }
  332.         }
  333.       node=node->child[id];
  334.     }
  335.     node->number_colors+=count;
  336.     p++;
  337.   }
  338.   if (file != (FILE *) NULL)
  339.     Histogram(cube.root,file);
  340.   /*
  341.     Release color cube tree storage.
  342.   */
  343.   do
  344.   {
  345.     nodes=cube.node_list->next;
  346.     (void) free((char *) cube.node_list);
  347.     cube.node_list=nodes;
  348.   }
  349.   while (cube.node_list != (Nodes *) NULL);
  350.   return(cube.colors);
  351. }
  352.